{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sqrt(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mySqrt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #x 的平方根 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个非负整数 <code>x</code> ，计算并返回&nbsp;<code>x</code>&nbsp;的 <strong>算术平方根</strong> 。</p>\n",
    "\n",
    "<p>由于返回类型是整数，结果只保留 <strong>整数部分 </strong>，小数部分将被 <strong>舍去 。</strong></p>\n",
    "\n",
    "<p><strong>注意：</strong>不允许使用任何内置指数函数和算符，例如 <code>pow(x, 0.5)</code> 或者 <code>x ** 0.5</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 4\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 8\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= x &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sqrtx](https://leetcode.cn/problems/sqrtx/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sqrtx](https://leetcode.cn/problems/sqrtx/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if x == 0 or x == 1:\n",
    "            return x\n",
    "        #find bound\n",
    "        length = int(math.log10(x))\n",
    "        left_side = int(math.pow(10, length//2))\n",
    "        right_side = int(math.pow(10, length//2 + 1))\n",
    "        \n",
    "        return self.recursive(x, left_side, right_side)\n",
    "    \n",
    "    def recursive(self,x, left_side, right_side):\n",
    "        \n",
    "        mid_pt = (left_side + right_side) // 2\n",
    "        if x == int(math.pow(left_side, 2)):\n",
    "            return left_side\n",
    "        elif x == int(math.pow(right_side, 2)):\n",
    "            return right_side\n",
    "        else:\n",
    "            mid_num = int(math.pow(mid_pt, 2))\n",
    "            if x == mid_num:\n",
    "                return mid_pt\n",
    "            elif x < mid_num:\n",
    "                if mid_pt - left_side <= 1:\n",
    "                    return left_side\n",
    "                else:\n",
    "                    right_side = mid_pt\n",
    "                    return self.recursive(x, left_side, right_side)\n",
    "            elif x > mid_num:\n",
    "                if right_side - mid_pt <= 1:\n",
    "                    return mid_pt\n",
    "                else:\n",
    "                    left_side = mid_pt\n",
    "                    return self.recursive(x, left_side, right_side)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if x <= 1:\n",
    "            return x\n",
    "        i = 1\n",
    "        h = x\n",
    "        while i <= h:\n",
    "            mid = int(i + (h - i) / 2)\n",
    "            sqrt = int(x / mid)\n",
    "            if sqrt == mid:\n",
    "                if mid - int(mid) < 0:\n",
    "                    return int(mid) - 1\n",
    "                else:\n",
    "                    return int(mid)\n",
    "            elif mid > sqrt:\n",
    "                h = mid - 1\n",
    "            else:\n",
    "                i = mid + 1\n",
    "        return int(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return int(x**0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        imin, imax = 0, x\n",
    "        while imin <= imax:\n",
    "            i = int((imin+imax)/2)\n",
    "            print(i)\n",
    "            if x == i*i:\n",
    "                return i\n",
    "                \n",
    "            elif x > i*i:\n",
    "                imin = i+1\n",
    "            else:\n",
    "                imax = i-1\n",
    "\n",
    "        if i*i > x:\n",
    "            return i-1\n",
    "        else:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if x < 2: return x\n",
    "        l, r = 0, x\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            print(l, r, mid)\n",
    "            if mid**2 > x:\n",
    "                r = mid-1\n",
    "            elif mid ** 2 <= x and (mid + 1) ** 2 > x:\n",
    "                return mid\n",
    "            else:\n",
    "                l = mid +1\n",
    "        return mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x <= 1:\n",
    "            return x\n",
    "        r = x\n",
    "        while r > x / r:\n",
    "            r = (r + x / r) // 2\n",
    "        return int(r)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return math.floor(math.sqrt(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if x == 0:\n",
    "            return 0\n",
    "\n",
    "        l = 1\n",
    "        r = x\n",
    "\n",
    "        while l <= x:\n",
    "            res = (l + r) // 2\n",
    "            s = res**2\n",
    "\n",
    "            if s <= x < (res + 1)**2:\n",
    "                return res\n",
    "            if s < x:\n",
    "                l = res\n",
    "            if s > x:\n",
    "                r = res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        from math import sqrt\n",
    "        return int(sqrt(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        rb = x\n",
    "        lb = 0\n",
    "        sol = 0\n",
    "        if x == 1:\n",
    "            return 1\n",
    "        while 1:  \n",
    "            if sol*sol <= x and (sol+1)*(sol+1) > x:\n",
    "                return sol\n",
    "            if (sol+1)*(sol+1) > x:\n",
    "                rb = sol\n",
    "                sol = int((sol+lb)/2)\n",
    "            else:\n",
    "                lb = sol\n",
    "                sol = int((sol+rb)/2)\n",
    "            print(sol)\n",
    "        return sol\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode id=69 lang=python3\n",
    "#\n",
    "# [69] Sqrt(x)\n",
    "#\n",
    "# https://leetcode.com/problems/sqrtx/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (30.46%)\n",
    "# Total Accepted:    322K\n",
    "# Total Submissions: 1.1M\n",
    "# Testcase Example:  '4'\n",
    "#\n",
    "# Implement int sqrt(int x).\n",
    "# \n",
    "# Compute and return the square root of x, where x is guaranteed to be a\n",
    "# non-negative integer.\n",
    "# \n",
    "# Since the return type is an integer, the decimal digits are truncated and\n",
    "# only the integer part of the result is returned.\n",
    "# \n",
    "# Example 1:\n",
    "# \n",
    "# \n",
    "# Input: 4\n",
    "# Output: 2\n",
    "# \n",
    "# \n",
    "# Example 2:\n",
    "# \n",
    "# \n",
    "# Input: 8\n",
    "# Output: 2\n",
    "# Explanation: The square root of 8 is 2.82842..., and since \n",
    "# the decimal part is truncated, 2 is returned.\n",
    "# \n",
    "# \n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: 'int') -> 'int':\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        else: \n",
    "            i = x / 2\n",
    "            for n in range(50):\n",
    "                i = (i + x/i) / 2\n",
    "            return int(i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        if x == 1:\n",
    "            return 1\n",
    "        y1 = x/2\n",
    "        y2 = x/y1 \n",
    "        while (y1-y2)>0.0000001:\n",
    "            y1 = (y1 + y2)/2 \n",
    "            y2 = x/y1\n",
    "        return int(y1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x<=1: #当x=0或1时\n",
    "            return x\n",
    "\n",
    "        left = 0\n",
    "        right = x\n",
    "        while(left<=right):\n",
    "            mid = (left+right)//2\n",
    "            if( mid**2<= x <(mid+1)**2):\n",
    "                return mid\n",
    "            elif x < mid**2:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x==0:\n",
    "            return 0\n",
    "        if x==1:\n",
    "            return 1\n",
    "        left=0\n",
    "        right=x\n",
    "        while True:\n",
    "            mid=int((left+right)/2)\n",
    "            if mid*mid<=x and (mid+1)*(mid+1)>x:\n",
    "                return mid\n",
    "            elif mid*mid<x:\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        result=int(x**(1/2))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if  x == 0:\n",
    "            return  0\n",
    "        elif    x == 1:\n",
    "            return  1\n",
    "        left,right = 1,x//2\n",
    "        #在[left,right]区域内进行二分搜索\n",
    "        #如果前面的x=0,x=1不单独考虑的情况下,将left设置为0,right设置为x//2+1即可\n",
    "        while   left <= right:\n",
    "        #因为两边都是闭区间,所以循环的条件为left <= right\n",
    "            mid = (left+right)//2\n",
    "            if  mid*mid == x:\n",
    "                return  mid\n",
    "            elif    mid*mid < x and (mid+1)*(mid+1) > x:\n",
    "                return  mid\n",
    "            elif    mid*mid > x:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        # 方法一\n",
    "        # return floor(sqrt(x))\n",
    "\n",
    "        # 方法二：\n",
    "        # if x <=1:\n",
    "        #     return x\n",
    "        # sqrt_x = x \n",
    "        # while x/sqrt_x < sqrt_x:\n",
    "        #     # 表示两数相除,向下取整\n",
    "        #     sqrt_x = (sqrt_x + x/sqrt_x)//2  \n",
    "        # return int(sqrt_x)\n",
    "\n",
    "        # 方法三\n",
    "        # 对给定的x作二分查找，如果它的半数的平方大于x，则继续折半\n",
    "        new_x = x//2\n",
    "        while new_x**2 > x:\n",
    "            new_x = new_x//2\n",
    "        # 如果折半后的平方小于x 且加1后的平方还是小于等于x，则新的x递增一\n",
    "        while new_x**2 < x and (new_x+1)**2 <= x:\n",
    "            new_x += 1\n",
    "        # 如果new_x的平方刚好等于x  或者 new_x的平方小于x 但同时new_x加一后的平方大于x,则直接返回new_x\n",
    "        if new_x**2 == x or (new_x**2 < x and (new_x+1)**2 > x):\n",
    "            return new_x\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l,r = 1,x\n",
    "        while l <= r:\n",
    "            mid = (l + r)//2\n",
    "            if mid * mid == x:\n",
    "                return mid\n",
    "            elif mid * mid < x:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        \n",
    "        return l if l * l < x else l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x==0:\n",
    "            return 0\n",
    "        for i in range(x+1):\n",
    "            if i*i ==x:\n",
    "                return i\n",
    "            if i*i>x:\n",
    "                return i-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def mySqrt(self, x: int) -> int:\r\n",
    "        return int(pow(x,0.5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        \"\"\"\n",
    "            x 的平方根\n",
    "            \n",
    "            实现 int sqrt(int x) 函数。\n",
    "            计算并返回 x 的平方根，其中 x 是非负整数。\n",
    "            由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。\n",
    "            \n",
    "            输入: 8\n",
    "            输出: 2\n",
    "            说明: 8 的平方根是 2.82842..., \n",
    "                 由于返回类型是整数，小数部分将被舍去。\n",
    "        \"\"\"\n",
    "        y = 1\n",
    "        while y ** 2 <= x:\n",
    "            y <<= 1\n",
    "        nums = [i for i in range(y >> 1, y + 1)]\n",
    "        return self.binarySearch(nums, x)\n",
    "\n",
    "    def binarySearch(self, nums, target):\n",
    "        \"\"\" 二分查找 \"\"\"\n",
    "        i, j = 0, len(nums) - 1\n",
    "        while i <= j:\n",
    "            in_middle = (j + i) // 2\n",
    "            pow_middle = nums[in_middle] ** 2\n",
    "            if pow_middle == target:\n",
    "                return nums[in_middle]\n",
    "            elif pow_middle < target:\n",
    "                i = in_middle + 1\n",
    "            else:\n",
    "                j = in_middle - 1\n",
    "\n",
    "        return nums[in_middle] if nums[in_middle] ** 2 < target else nums[in_middle] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.com/explore/learn/card/binary-search/125/template-i/950/\n",
    "import os, sys, shutil, glob, re\n",
    "import time, calendar\n",
    "from datetime import datetime, timezone\n",
    "import hashlib, zipfile, zlib\n",
    "from math import *\n",
    "from operator import itemgetter\n",
    "from functools import wraps, cmp_to_key\n",
    "from itertools import count, combinations, permutations\n",
    "from collections import namedtuple, defaultdict, Counter\n",
    "from queue import Queue\n",
    "\n",
    "# 其实是要找upper_bound\n",
    "def binarySearch(left, right, target):\n",
    "  while left < right:\n",
    "    mid = right - (right-left) // 2\n",
    "    if mid ** 2 > target:\n",
    "      right = mid - 1\n",
    "    else:\n",
    "      left = mid\n",
    "  return left\n",
    "\n",
    "class Solution:\n",
    "  def mySqrt(self, x):  # -> int\n",
    "    return binarySearch(0, x, x)\n",
    "\n",
    "\n",
    "if __name__ == '__main__' and ('SJDEAK' in os.environ):\n",
    "  from utils.tree import TreeNode, array2TreeNode\n",
    "\n",
    "\n",
    "  def test(*args):\n",
    "    print('输入数据: ', *args)\n",
    "    print('结果: ', Solution().mySqrt(*args), end='\\n-----\\n')\n",
    "\n",
    "\n",
    "  test(8)\n",
    "  test(2)\n",
    "  test(9)\n",
    "  test(0)\n",
    "  test(1)\n",
    "else:\n",
    "  print = lambda *args, **kwargs: None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(x ** (1 / 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "      l, r, ant = 0, x, 0\n",
    "      while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        if mid ** 2 <= x:\n",
    "          ant = mid\n",
    "          l = mid + 1\n",
    "        else:\n",
    "          r = mid - 1\n",
    "      return ant"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left, right = 0, x\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mid * mid == x: return mid\n",
    "            elif mid * mid < x:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        low = 1\n",
    "        high = x\n",
    "        while 1:\n",
    "            mid = (low + high) // 2\n",
    "            if mid*mid <= x:\n",
    "                if x < (mid + 1)*(mid + 1):\n",
    "                    return mid\n",
    "                else:\n",
    "                    low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        # arr_pow = list(map(lambda y: y * y, range(46341)))\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        if x == 1:\n",
    "            return 1\n",
    "\n",
    "        left, right = 1, x / 2\n",
    "        while left < right:\n",
    "            middle = left + (right - left) / 2\n",
    "            print(middle)\n",
    "            if middle > x / middle:\n",
    "                right = middle  # 下次在[left, middle]找\n",
    "            elif middle < x / middle:\n",
    "                left = middle  # 下次在[middle, right]找\n",
    "            else:\n",
    "                return int(middle)\n",
    "\n",
    "            if int(left) == int(right):\n",
    "                break\n",
    "\n",
    "\n",
    "        return int(left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left,right,result=0,x,-1\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if mid*mid<=x:\n",
    "                result = mid\n",
    "                left=mid+1\n",
    "            else:right=mid-1\n",
    "        return result\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "\n",
    "        if x == 1 or x == 0:\n",
    "            return x\n",
    "\n",
    "        start = 1\n",
    "        end = x\n",
    "        mid = x // 2\n",
    "\n",
    "        while start <= end:\n",
    "            if mid * mid <= x and (mid+1) * (mid+1) > x:\n",
    "                return mid\n",
    "            if mid * mid > x:\n",
    "                end = mid\n",
    "                mid = (start + end) // 2\n",
    "            else:\n",
    "                start = mid\n",
    "                mid = (start + end) // 2\n",
    "        return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x==0:\n",
    "            ans=0\n",
    "        l,r=0,x+1\n",
    "        k=4\n",
    "        while l+1<r:\n",
    "            i=(l+r)//2\n",
    "            if i*i==x:\n",
    "                ans=i\n",
    "                break\n",
    "            elif i*i>x:\n",
    "                r=i\n",
    "            else:\n",
    "                l=i\n",
    "            ans=l\n",
    "        return ans \n",
    "                \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        # # 方法1：使用内置函数sqrt（）\n",
    "        # mun = math.sqrt(x)\n",
    "        # ans = str(mun).split(\".\")\n",
    "        # return int(ans[0])\n",
    "\n",
    "        # 方法2：二分查找法\n",
    "        l = 0\n",
    "        r = x\n",
    "        ans = -1\n",
    "        while l <= r:\n",
    "            mind = (l+r) // 2\n",
    "            if mind*mind <= x:\n",
    "                ans = mind\n",
    "                l = mind + 1\n",
    "            else:\n",
    "                r = mind - 1\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
